package com.xq.algorithm.string;

/**
 * @author jltxseo
 *         Created by junlintianxia on 2017/07/10.
 *         给定一个字符串，这个字符串为*号和26个字母的任意组合。现在需要把字符串的*号都移动到最左侧，而把字符串中的字母移动到最右侧并保持相对顺序不变，要求时间复杂度和空间复杂度最小。
 *         解题思路：
 *         用point表示尾部的第一个*的位置， let表示point之前的第一个字母的位置，依次交换point和let指向的元素，再找下一组*和字母的序列，直到point和let有一个指向字符串的首地址。
 *
 */

public class MoveStrAlgorithm {

    /**
     * 从后往前扫描，把距*之前最近的字母相交换，可以保证次序。
     * @param ch
     * @param len
     */
    public static void moveChar(char[] ch,int len)
    {
        int point=len-1;
        int let=len-1;

        while(point!=0&&let!=0)
        {
            while(ch[point]!='*'&&point!=0)  //first * from the end
            {
                point--;
            }
            if(point==0)             //all ch are *
                return;
            let=point;
            while(ch[let]=='*'&&let!=0)   //the first letter before *
            {
                let--;
            }
            while(ch[let]!='*'&&ch[point]=='*')
            {
                char tem=ch[let];
                ch[let]=ch[point];
                ch[point]=tem;
                if(point!=0)
                    point--;
                if(let!=0)
                    let--;
            }
        }
    }

    public static void main(String[] args)
    {
        String str="abc**gh*58*r";
        char[] ch=str.toCharArray();
        moveChar(ch,str.length());
        System.out.println(ch);
    }
}
